package com.mango.algorithm.partition;

import java.util.Arrays;

/**
 * 荷兰国旗问题
 * @Author: mango
 * @Date: 2022/5/15 9:20 上午
 */
public class DutchFlag {
    public static void main(String[] args) {
        int[] arr = {3,6,2,4,8,1,4};
        //partition1(arr,4);
        //System.out.println(Arrays.toString(arr));
        partition2(arr,4);
        System.out.println(Arrays.toString(arr));
    }
    public static void partition2(int[] arr,int num){
        // left表示左侧区域,i是遍历指针
        int left = -1;
        int right = arr.length;
        int i = 0;
        while (i < right){
            if(arr[i] < num){
                // 小于当前数的，交换指针位置和小于区域下一个位置，小于区域和指针右移
                swap(arr,++left,i++);
            }else if(arr[i] == num){
                i++; // 等于num，指针右移
            }else{
                // 大于当前数的，指针和大于区域前一位交换，大于区域左移
                swap(arr,--right,i);
            }
        }
    }
    /**
     * 问题1：
     * 给定一个数组arr，和一个数num，请把小于等于于num的数放在数组的左边，大于num的数放在数组的右边。
     * 要求额外空间复杂度O(1)，时间复杂度O(N)。
     */
    public static void partition1(int[] arr,int num){
        // left表示左侧区域,i是遍历指针
        int left = -1;
        int i = 0;
        while (i < arr.length){
            if(arr[i] <= num){
                // 交换指针位置和小于区域下一个位置，小于区域和指针右移
                swap(arr,++left,i++);
            }else{
                i++; // 大于num，指针右移
            }
        }
    }
    // 异或交换
    private static void swap(int[] arr,int i,int j){
        if(i == j){
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}
